package list

/*
	输入一个链表，输出该链表中倒数第k个节点。为了符合大多数人的习惯，本题从1开始计数，即链表的尾节点是倒数第1个节点。例如，一个链表有6个节点，从头节点开始，它们的值依次是1、2、3、4、5、6。这个链表的倒数第3个节点是值为4的节点。

	示例：

	给定一个链表: 1->2->3->4->5, 和 k = 2.

	返回链表 4->5.

*/
// 递归，在走到最终的空节点时，给定count为0，在向回走的时候count++，即：头节点count为1，头节点的前节点count为2，一直往回走，走到count=k
var count int
var lnode *ListNode
func GetKthFromEnd(head *ListNode, k int) *ListNode {
	//twoPointGetKthFromEnd(head, k)
	return twoPointGetKthFromEnd(head, k)
}

func recursiveGetKthFromEnd(node *ListNode, k int) *ListNode {
	if nil == node {
		return node
	}
	recursiveGetKthFromEnd(node.Next, k)
	count++
	if count == k {
		lnode = node
		return node
	}
	return nil
}

// twoPoint
func twoPointGetKthFromEnd(head *ListNode, k int) *ListNode {
	p,q := head, head
	c := 0
	for p != nil {
		p = p.Next
		c++
		if c > k {
			q = q.Next
		}
	}
	return q
}
